#
# @lc app=leetcode.cn id=327 lang=python3
#
# [327] 区间和的个数
#
from typing import List


# @lc code=start
class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        def mergeCount(arr: List[int]):
            n = len(arr)
            if n <= 1:
                if n == 1 and lower <= arr[0] <= upper:
                    return 1
                else:
                    return 0

            arr1 = arr[:n // 2]
            arr2 = arr[n // 2:]
            cnt = mergeCount(arr1) + mergeCount(arr2)

            n1 = len(arr1)
            n2 = len(arr2)
            left = 0
            for v in arr1:
                while left < n2 and arr2[left] - v < lower:
                    left += 1
                right = left
                while right < n2 and arr2[right] - v <= upper:
                    right += 1
                cnt += right - left

            p1 = p2 = i = 0
            while i < n:
                if p1 < n1 and (p2 == n2 or arr1[p1] < arr2[p2]):
                    arr[i] = arr1[p1]
                    p1 += 1
                else:
                    arr[i] = arr2[p2]
                    p2 += 1
                i += 1

            return cnt

        prefixSum = [0]
        for i in nums:
            prefixSum.append(prefixSum[-1] + i)
        return mergeCount(prefixSum[1:])


# @lc code=end
if __name__ == "__main__":
    s = Solution()
    nums = [-2, 5, -1]
    lower = -2
    upper = 2
    ret = s.countRangeSum(nums, lower, upper)
    print(ret, 3)

    nums = []
    lower = 0
    upper = 0
    ret = s.countRangeSum(nums, lower, upper)
    print(ret, 0)
    